import java.util.Arrays;
import java.util.Comparator;

class Item {
    int weight;//物品重量
    public int value;//物品价值
    //初始化物品
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

public class Knapsack {
    //计算背包问题的最大价值
    public static double getMaxValue(Item[] items, int capacity) {
        // 按照单位价值（价值重量比）进行排序，从高到低

        Arrays.sort(items, (item1, item2) -> {
            double ratio1 = (double) item1.value / item1.weight;
            double ratio2 = (double) item2.value / item2.weight;
            // 降序排序
            if (ratio1 < ratio2) {
                return 1;
            } else if (ratio1 > ratio2) {
                return -1;
            } else {
                return 0;
            }
        });

        double totalValue = 0;//背包中物品的总价值
        int currentCapacity = capacity;//剩余背包容量

        for (Item item : items) {
            //背包优先选择单位价值高的物品
            //如果它的重量小于等于当前背包的剩余容量，就将整个物品放入背包，并更新总价值和剩余容量
            if (item.weight <= currentCapacity) {
                // 将整个物品放入背包
                totalValue += item.value;
                currentCapacity -= item.weight;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {new Item(10, 60),//单位价值6
                new Item(20, 100),//5
                new Item(5, 15),//3
                new Item(7, 7),//1
                new Item(10, 60),//6
                new Item(3, 12),//4
                new Item(30, 150)};//5
        int capacity = 40;
        double maxValue = getMaxValue(items, capacity);
        System.out.println("背包中物品最大总价值为: " + maxValue);
    }
}
